home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programmierung
/
Power-Programmierung (Tewi)(1994).iso
/
magazine
/
pctchnqs
/
1992
/
number1
/
splay.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-02-06
|
5KB
|
200 lines
/* Splay tree implementation
Translated from the initial Pascal version by Andrew M. Liao
The splay routines are called in the following manner:
root=splay(arg,root); Search
root=splayinsert(arg,root); Insert
root=splaydelete(arg,root); Delete
*/
#define TESTING /* comment if not testing */
#include <stdlib.h>
#define key long
struct node { long data; struct node *left,*right; };
struct nrec { struct node *left,*right; };
#define false 0
#define true 1
struct node *rrot(root)
struct node *root;
{ struct node *temp,*temp1,*p;
p=root;
if (p!=NULL)
{ if (p->left!=NULL)
{ temp=p; temp1=p->left->right;
p=temp->left; p->right=temp; temp->left=temp1;
}
}
return(p);
}
struct node *lrot(root)
struct node *root;
{ struct node *temp,*temp1,*p;
p=root;
if (p!=NULL)
{ if (p->right!=NULL)
{ temp=p; temp1=p->right->left;
p=temp->right; p->left=temp; temp->right=temp1;
}
}
return(p);
}
struct node *lnkright(root,r)
struct node *root;
struct nrec *r;
{ struct node *temp,*p;
p=root;
if (p->left!=NULL)
{ temp=p->left; p->left=NULL;
if (r->left==NULL)
{ r->left=p; r->right=p; }
else
{ r->right->left=p; r->right=r->right->left; }
p=temp;
}
return(p);
}
struct node *lnkleft(root,l)
struct node *root;
struct nrec *l;
{ struct node *temp,*p;
p=root;
if (p->right!=NULL)
{ temp=p->right; p->right=NULL;
if (l->left==NULL)
{ l->left=p; l->right=p; }
else
{ l->right->right=p; l->right=l->right->right; }
p=temp;
}
return(p);
}
struct node *assemble(p,l,r)
struct node *p;
struct nrec *l,*r;
{ struct node *temp,*temp1;
temp=p->left; temp1=p->right;
if (l->left!=NULL)
{ p->left=l->left; l->right->right=temp; }
if (r->left!=NULL)
{ p->right=r->left; r->right->left=temp1;}
}
struct node *splay(x,root)
key x;
struct node *root;
{ struct nrec l,r; /* Temp subtrees */
struct node *p;
int done; /* Process boolean */
p=root;
l.left=l.right=r.left=r.right=NULL;
done=false;
if (p!=NULL)
{ do
{if (x<p->data)
{ if (p->left!=NULL)
{ if (x==p->left->data) p=lnkright(p,&r);
else
if (x<p->left->data)
{ p=rrot(p); p=lnkright(p,&r); }
else
if (x>p->left->data)
{ p=lnkright(p,&r); p=lnkleft(p,&l); }
} else done=true;
}
else
if (x>p->data)
{ if (p->right!=NULL)
{ if (x==p->right->data) p=lnkleft(p,&l);
else
if (x>p->right->data)
{ p=lrot(p); p=lnkleft(p,&l); }
else
if (x<p->right->data)
{ p=lnkleft(p,&l); p=lnkright(p,&r); }
} else done=true;
}
}
while ((p->data!=x) && !done);
assemble(p,&l,&r);
}
return(p);
}
struct node *splayinsert(x,root)
key x;
struct node *root;
{ struct node *p;
struct node foo;
root=splay(x,root);
if ((root==NULL) || (root->data!=x))
{ p=(struct node *) malloc(sizeof(foo));
p->data=x; p->left=p->right=NULL;
if ((root!=NULL) && (x<root->data))
{ p->right=root; p->left=root->left;
root->left=NULL;
}
else
if ((root!=NULL) && (x>root->data))
{ p->left=root; p->right=root->right;
root->right=NULL;
}
root=p;
}
return(root);
}
/* NOTE: SPLAYDELETE is currently set up to deal with integer keys.
if you want to deal with strings, you will have to build an
appropriate character array all of whose bytes have the maximum
ASCII value on you machine. */
struct node *splaydelete(x,root)
key x;
struct node *root;
{ struct node *temp1,*temp2;
key max=2147483647;
root=splay(x,root);
if ((root!=NULL) && (root->data==x))
{ temp1=root->left; temp2=root->right;
if (temp1!=NULL)
{ temp1=splay(max,temp1);
temp1->right=temp2;
} else temp1=temp2;
free((char *) root);
root=temp1;
}
return(root);
}
#ifdef TESTING
void main (void) {
int x;
key z;
struct node *root = NULL;
puts ("fill tree");
root = splayinsert (-1L, root);
for (x=0; x<10; x++) {
z = random (10);
root = splayinsert (z, root);
printf ("%02ld ", root->data);
}
puts ("\nsearch tree");
for (x=0; x<100; x++) {
z = random (10);
root = splay (z, root);
printf ("Search for %02ld. %sfound. Root = %02ld\n", z,
(root->data == z) ? " " : "Not ", root->data);
}
puts ("\ndone");
}
#endif